﻿/*
 * Rappelz: Endless Odyssey - The first free open source Rappelz server emulator
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Rappelz.GameServer
{
    public class QuadTreeScanner
    {
        public class Node
        {
            public Node(ushort _depth, float _left, float _right, float _top, float _bottom)
            {
                this.left = _left;
                this.depth = _depth;
                this.right = _right;
                this.top = _top;
                this.bottom = _bottom;
                this.pNode[0, 0] = null;
                this.pNode[1, 0] = null;
                this.pNode[0, 1] = null;
                this.pNode[1, 1] = null;
                this.bIsLeafNode = true;
            }
            
            public Node getLeafNode(float x, float y)
            {
                if (this.bIsLeafNode)
                    return this;

                int rx = 0;
                int ry = 0;

                if ((this.right - this.left) * 0.5f + this.left <= x)
                    rx = 1;

                if ((this.bottom - this.top) * 0.5f + this.top <= y)
                    ry = 1;

                return pNode[rx, ry];
            }
            
/*
            public void Scan(float, float, float, float, List<Creature.QuadTreeItem> &)
            {
            }
*/
            
            public void Add(Creature.QuadTreeItem t)
            {
                if (this.depth == 10 || this.top <= t.y && this.bottom > t.y && this.left <= t.x && this.right > t.x)
                {
                    Node ln = this.getLeafNode(t.x, t.y);
                    ln.pvList.Add(t);
                    if (this.depth != 10)
                    {
                        if (ln.pvList.Count > 100)
                            ln.Divide();
                    }
                }
            }

            public bool Remove(Creature.QuadTreeItem t)
            {
                if (this.depth == 10 || this.top <= t.y && this.bottom > t.y && this.left <= t.x && this.right > t.x)
                {
                    Node ln = getLeafNode(t.x, t.y);
                    if (ln != null && ln.pvList != null)
                    {
                        if(ln.pvList.Contains(t))
                        {
                            ln.pvList.Remove(t);
                            return true;
                        }
                    }
                }
                return false;
            }
            
            public bool IsExist(Creature.QuadTreeItem t)
            {
                return IsExist(t.x, t.y);
            }

            public bool IsExist(float x, float y)
            {
                Node ln = getLeafNode(x,y);
                if(ln == null)
                    return false;
                foreach (Creature.QuadTreeItem item in ln.pvList)
                {
                    if((float)item.x == x && (float)item.y == y)
                        return true;
                }
                return false;
            }
            
            public void Divide()
            {
                if (this.depth < 10)
                {
                    this.bIsLeafNode = false;
                    this.pNode[0, 0] = new Node((ushort)(this.depth + 1), this.left, (this.right - this.left) * 0.5f + this.left, this.top, (this.bottom - this.top) * 0.5f + this.top);
                    this.pNode[1, 0] = new Node((ushort)(this.depth + 1), (this.right - this.left) * 0.5f + this.left, this.right, this.top, (this.bottom - this.top) * 0.5f + this.top);
                    this.pNode[0, 1] = new Node((ushort)(this.depth + 1), this.left, (this.right - this.left) * 0.5f + this.left, (this.bottom - this.top) * 0.5f + this.top, this.bottom);
                    this.pNode[1, 1] = new Node((ushort)(this.depth + 1), (this.right - this.left) * 0.5f + this.left, this.right, (this.bottom - this.top) * 0.5f + this.top, this.bottom);

                    foreach (Creature.QuadTreeItem item in this.pvList)
                    {
                        this.Add(item);
                    }
                    this.pvList.Clear();
                }
            }

            public bool bIsLeafNode;
            public ushort depth;
            public float left;
            public float right;
            public float top;
            public float bottom;
            public Node[,] pNode = new Node[2, 2];
            public List<Creature.QuadTreeItem> pvList = new List<Creature.QuadTreeItem>();
        }

        public QuadTreeScanner(float width, float height)
        {
            m_Node = new Node(0, 0.0f, width, 0.0f, height);
            this.m_nWidth = width;
            this.m_nHeight = height;
        }

        public void Add(Creature.QuadTreeItem t)
        {
            lock(this)
            {
                this.m_Node.Add(t);
            }
        }

        public bool IsExist(float x, float y)
        {
            lock(this)
            {
                return m_Node.IsExist(x,y);
            }
        }

        public bool IsExist(Creature.QuadTreeItem t)
        {
            lock(this)
            {
                return m_Node.IsExist(t);
            }
        }

        public bool Remove(Creature.QuadTreeItem t)
        {
            lock(this)
            {
                return m_Node.Remove(t);
            }
        }

/*
        public void Scan(float, float, float, float, List<Creature.QuadTreeItem> &)
        {

        }
*/

        public float m_nWidth;
        public float m_nHeight;
        public Node m_Node;
    }
}
